// 有一堆石头，每块石头的重量都是正整数。
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
// 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
// 输入：[2,7,4,1,8,1]
// 输出：1
// 解释：

// 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
// 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
// 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
// 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值

// 思路，动态规划，01背包
// 该题的思路是把一堆石头分为重量尽量相同的两堆，这样两堆相撞后剩下的石头最小，这个又可以转换位01背包的问题
// 示例：


// 五部曲
// 1. `dp[j]`，大小为j的背包，最多可以容纳多少重量的石头
// 2. 递推公式`dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])`
// 3. 初始化，0
// 4. 遍历顺序，物品在外层遍历，背包在内层遍历，且应该为倒序遍历
// 5. 举例推导
function lastStoneWeightII(stones) {
    let sum = stones.reduce((sum, cur) => sum + cur)
    let target = Math.floor(sum / 2)
    let dp = new Array(target + 1).fill(0)
    for (let i = 0; i < stones.length; i++) {
        for (let j = target; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])            
        }        
    }
    return sum - dp[target] - dp[target]
}

console.log(lastStoneWeightII([2,7,4,1,8,1]))